package test;

/**
 * Created by louisgeek on 2017/3/20.
 */
public class JiaoHuanSort {

    public static final int[] arr = {4, 3, 6, 7, 1, 2, 5};


    public static void main(String[] args) {
        //## sortMaoPao_Bubble();
        //## sortMaoPao_Bubble_New();
        //sortKuaiSu_Quick();
        sortKuaiSu_Quick2();

    }

    private static void outArr() {
        StringBuffer stringBuffer = new StringBuffer();
        for (int i = 0; i < arr.length; i++) {
            stringBuffer.append(arr[i]);
        }
        System.out.println("arr:" + stringBuffer.toString());
    }

    private static void exChange(int fromPos, int toPos) {
        int temp = arr[fromPos];
        arr[fromPos] = arr[toPos];
        arr[toPos] = temp;
    }


    /**
     *
     */
    public static void sortMaoPao_Bubble() {
        for (int i = 0; i < arr.length - 1; i++) {//循环 arr.length-1 轮
            for (int j = 0; j < arr.length - 1 - i; j++) { //逐一递减  循环次数
                if (arr[j] > arr[j + 1]) {
                    exChange(j, j + 1);//交换
                }
            }
        }
        outArr();
    }

    /**
     * 带标记  及时停止不必要的循环
     */
    public static void sortMaoPao_Bubble_New() {
        boolean hasExChange = false;
        for (int i = 0; i < arr.length - 1; i++) {//循环 arr.length-1 轮
            for (int j = 0; j < arr.length - 1 - i; j++) { //逐一递减  循环次数
                if (arr[j] > arr[j + 1]) {
                    exChange(j, j + 1);//交换
                    hasExChange = true;
                }
            }
            if (!hasExChange) {
                //未交换
                System.out.println(" ! hasExChange i:" + i);
                break;
            }
        }
        outArr();
    }

    /**
     *
     */
    public static void sortKuaiSu_Quick() {
        quickSort(0, arr.length - 1);
        outArr();
    }
    private static void quickSort(int left_pos, int right_pos) {
        if (left_pos >= right_pos) {
            return;
        }
        int left_pos_temp = left_pos;
        int right_pos_temp = right_pos;
        int X = arr[left_pos_temp];//基准值
        //开始
        while (left_pos_temp < right_pos_temp) {
            //从右边开始
            while (left_pos_temp < right_pos_temp && !(arr[right_pos_temp] <= X)) {//不满足  <= X  持续--
                right_pos_temp--;
            }
            //
            if (left_pos_temp < right_pos_temp) {
                arr[left_pos_temp] = arr[right_pos_temp];
            }
            //
            while (left_pos_temp < right_pos_temp && !(arr[left_pos_temp] > X)) {//不满足  > X  持续--
                left_pos_temp++;
            }
            if (left_pos_temp < right_pos_temp) {
                arr[right_pos_temp] = arr[left_pos_temp];
            }
        }
        //跳出循环 时候  left_pos_temp==right_pos_temp
        arr[left_pos_temp] = X;
        int X_pos = left_pos_temp;//当前基准值的pos

        //分别继续递归两侧数组
        quickSort(left_pos, X_pos - 1);//X_pos 基准值以前
        quickSort(X_pos + 1, right_pos);//X_pos 基准值以后

    }

    /**
     *
     */
    public static void sortKuaiSu_Quick2() {
        quickSort_Recursive(0, arr.length - 1);
        outArr();
    }

    public static void quickSort_Recursive(int left_pos, int right_pos) {
        if (left_pos >= right_pos) {
            return;
        }
        int pivot = quickSort_Partition(left_pos, right_pos);
        //##
        quickSort_Recursive(left_pos, pivot - 1);
        quickSort_Recursive(pivot + 1, right_pos);
    }

    private static int quickSort_Partition(int left_pos, int right_pos) {

        int X = arr[left_pos];//基准值
        //开始
        while (left_pos < right_pos) {
            //从右边开始
            while (left_pos < right_pos && !(arr[right_pos] <= X)) {//不满足  <= X  持续--
                right_pos--;
            }
            //
            if (left_pos < right_pos) {
                arr[left_pos] = arr[right_pos];
            }
            //
            while (left_pos < right_pos && !(arr[left_pos] > X)) {//不满足  > X  持续--
                left_pos++;
            }
            if (left_pos < right_pos) {
                arr[right_pos] = arr[left_pos];
            }
        }
        //跳出循环 时候  left_pos_temp==right_pos_temp
        arr[left_pos] = X;
        int X_pos = left_pos;//当前基准值的pos

        return X_pos;
    }

}
